"""
题目：实现二叉树的层序遍历（按层次从上到下，同一层从左到右），返回遍历结果。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def create_binary_tree(arr):
    """根据插入建立的列表数据 创建二叉树（层序遍历方式）"""
    if not arr:
        return None
    # 创建根节点
    root = TreeNode(arr[0])
    # 使用队列存储待处理节点
    queue = [root]
    index = 1  # 当前处理的列表索引
    while queue and index < len(arr):
        # 取出当前队列中的首节点，注意，pop是会清掉对应的数据的
        current = queue.pop(0)
        # 处理左子节点
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            #注意：只有非None节点，才会被加入queue中，这样就能保证：None节点本身不会再有左子树、右子树了
            queue.append(current.left)
        index += 1
        # 处理右子节点（检查是否还有元素,因为index已经加过1了，需要再次检查是否超过arr长度）
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
        #因为是二叉树，所以，每次pop出来的队列中的首节点，只需要判断处理2次，一次左子树，一次右子树。
    return root


# 测试
# 列表表示：[1, 2, 3, None, 4, 5, None]
# 对应的树结构：
#       1
#      / \
#     2   3
#      \ /
#      4 5
root = create_binary_tree([1, 2, 3, None, 4, 5, None])
print(root.val)  # 输出: 1
print(root.left.val)  # 输出: 2
print(root.right.val)  # 输出: 3
print(root.left.right.val)  # 输出: 4
print(root.right.left.val)  # 输出: 5